Explain Open Addressing. (Linear Probing, Quadratic Probing, Double Hashing)

Open Addressing

javascript

1
Linear probing checks consecutive slots and has good cache locality but can suffer from primary clustering.
2
Quadratic probing uses increasing probe distances and reduces primary clustering.
3
Double hashing uses a second hash function to produce a more independent probe sequence.
4
Open addressing requires careful handling of deletion, often using tombstones.
5
Performance degrades as the table becomes too full.
6
Resizing is generally necessary at a lower load factor than with some chaining implementations.

Difficulty: 5/10

Topics: collision resolution, probing strategies, hash table performance

0-2 years experience

1
Suppose you need to implement a hash map for a small in‑memory cache using open addressing with linear probing. How would you handle inserting a new key when the initial slot is already occupied?
2
If you use quadratic probing and the table size is a prime number, what could happen when the load factor reaches 0.9? How would you detect and resolve it?
3
What happens if you try to delete a key in a hash table that uses linear probing without any special handling? Explain the issue.

2-5 years experience

1
Your team added a feature that stores user sessions in a hash table using double hashing. After a deployment, you notice a spike in lookup latency. Walk me through how you would debug the probing sequence to find the root cause.
2
When choosing between linear probing and quadratic probing for a hash table that will store up to 1 million entries, what trade‑offs would you consider regarding clustering and cache performance?
3
During a load test, the hash table's load factor exceeds 0.75 and insertions start failing. How would you modify the open addressing implementation to handle this gracefully?

5-8 years experience

1
Design a high‑throughput in‑memory key‑value store that uses open addressing. How would you decide which probing strategy to use, and what mechanisms would you add to keep performance stable under an 80% load factor?
2
Explain how you would implement safe deletions in a hash table that uses double hashing in a multi‑threaded environment, ensuring no lost keys and minimal contention.
3
Your service must support hot‑key skew where a few keys are accessed millions of times per second. How does open addressing affect this pattern, and what mitigations would you apply?

8+ years experience

1
Our legacy system uses linear probing and is being migrated to a distributed cache. What architectural considerations would you evaluate when deciding whether to keep open addressing locally or replace it with a different data structure across nodes?
2
When scaling a global hash table that uses double hashing, how would you handle rehashing and probing across rolling upgrades without downtime?
3
Discuss the long‑term maintenance implications of using open addressing in a codebase that must support multiple languages and platforms. How would you standardize the implementation to avoid subtle bugs?

❓How does the choice of probing strategy affect cache locality?
❓What are the implications of using a non‑prime table size with double hashing?
❓Can you compare the expected number of probes for each method at 50% load factor?